\documentclass[revised]{FPSAC2017}

\articlenumber{68}
\addbibresource{68_Ceballos_Padrol_Sarmiento.bib}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{color}
\usepackage{enumitem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% newtheorems

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{algorithm}[theorem]{Algorithm}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{openproblem}[theorem]{Open Problem}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}
\newtheorem{comment}[theorem]{Comment}
\newtheorem{observation}[theorem]{Observation}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% newcommands

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%special letters

%blackboardboldface

\newcommand{\0}{\mathbf{0}}
\newcommand{\1}{\mathbf{1}}

\newcommand{\kk}{\mathbb{k}}

\newcommand{\CC}{\mathbb{C}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\TT}{\mathbb{T}}
\newcommand{\ZZ}{\mathbb{Z}}

\newcommand{\TP}{\mathbb{TP}}

%calligraphic

\newcommand{\cC}{\mathcal{C}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}

%boldface

\newcommand{\bfa}{\mathbf{a}}
\newcommand{\bfb}{\mathbf{b}}
\newcommand{\bfe}{\mathbf{e}}
\newcommand{\bfel}{\ol{\mathbf{e}}}
\newcommand{\bfg}{\mathbf{g}}
\newcommand{\bfh}{\mathbf{h}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bfv}{\mathbf{v}}
\newcommand{\bfw}{\mathbf{w}}
\newcommand{\bfx}{\mathbf{x}}

\newcommand{\bfA}{\mathbf{A}}
\newcommand{\bfB}{\mathbf{B}}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfD}{\mathbf{D}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfL}{\mathbf{L}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}

%\fraktur
\newcommand{\frm}{\mathfrak{m}}

\newcommand{\frC}{\mathfrak{C}}

\newcommand{\frD}{\mathfrak{D}}
\newcommand{\frJ}{\mathfrak{J}}
\newcommand{\frO}{\mathfrak{O}}
\newcommand{\frP}{\mathfrak{P}}
\newcommand{\frT}{\mathfrak{T}}

%sf
\newcommand{\sfg}{\mathsf{g}}

\newcommand{\sfT}{\mathsf{T}}
\newcommand{\sfN}{\mathsf{N}}
\newcommand{\sfE}{\mathsf{E}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%math notation

% geometry/simplicial complexes
\DeclareMathOperator{\conv}{conv} % convex hull
\DeclareMathOperator{\vol}{vol} % volume
\DeclareMathOperator{\supp}{supp} % support of polyhedral complex
\DeclareMathOperator{\lspan}{span} % linear span
\DeclareMathOperator{\link}{link} % link of face in simplicial complex

\DeclareMathOperator*{\argmin}{arg\,min}

% big join operator
\newcommand{\bigast}{%
  \mathop{ % we want it to be an operator
    \mathchoice{\dobigast\huge}
               {\dobigast\large}
               {\dobigast\normalsize}
               {\dobigast\small}
    }\displaylimits % not necessary, but added for clarity
}

\newcommand{\dobigast}[1]{%
  \vcenter{#1\kern.2ex\hbox{$\ast$}\kern.2ex}}


% catalan combinatorics

\newcommand{\catnum}[1]{{C}_{#1}} % Catalan number
\newcommand{\ratcatnum}[2]{{C}{(#1,#2)}} % rational Catalan number
\newcommand{\ngonp}[1]{P_{#1}}
\newcommand{\ngon}{\ngonp{n+1}}
\newcommand{\twongon}{\ngonp{2n}}
\newcommand{\cyctri}[1]{\mathfrak{C}_{#1}}

\newcommand{\nudyckp}[1]{\mathsf{Dyck}_{#1}}
\newcommand{\nudyck}{\nudyckp{\nu}}

\newcommand{\rootpoly}[1]{Q_{#1}}

% triangulations of products of simplices

\newcommand{\catblock}[1]{\mathcal{U}_{#1}}% %"catalan subpolytope" of the product of simplices

\newcommand{\productp}[2]{\Delta_{{#1}}\times\Delta_{{#2}}} % product of simplices with parameters
\newcommand{\product}{\productp{n}{\ol m}} % product of simplices
\newcommand{\productn}{\productp{n}{\ol n}} % product of simplices of the same size
\newcommand{\productIJ}{\productp{I}{\ol J}}

\newcommand{\skel}{\mathrm{skel}} % this will possibly be removed
\newcommand{\kskel}[2]{\Delta_{#1}^{({#2})}}
\newcommand{\semiskelp}[3]{\Delta_{{#1}}^{({#3})}\times\Delta_{{#2}}} %semi-skeleton with parameters
\newcommand{\semiskel}{\semiskelp{d}{n}{k}} % semi-skeleton

\newcommand{\bipartite}{\bipartitep{n}{m}} %complete bipartite graph
\newcommand{\bipartitep}[2]{K_{{#1},{\overline #2}}} %complete bipartite graph with parameters
\newcommand{\bipartiteb}{\bipartitebp{n}{m}} %complete bipartite graph with brackets
\newcommand{\bipartitebn}{\bipartitebp{n}{n}} %complete bipartite graph with equal brackets
\newcommand{\bipartitebp}[2]{K_{{[#1]},{[\overline #2]}}} %complete bipartite graph with parameters and brackets
\newcommand{\bipartiteij}{\bipartitep{I}{J}} % complete bipartite graph with parts I, \ol J

\newcommand{\gr}[2]{\boxplus_{{#1}\times {#2}}} % grid with parameters
\newcommand{\gridn}{\gr{n}{n}}


\newcommand{\dyckptri}[1]{\boldsymbol{\mathfrak{D}}_{#1}} % dyck path triangulation

\newcommand{\asstri}[1]{{\mathfrak{A}}_{#1}} % associahedral triangulation

\newcommand{\asscomp}[1]{{\mathcal{A}}_{#1}}%tamari complex

\newcommand{\cyclotri}[1]{{\mathfrak{C}}_{#1}}%cyclohedral triangulation

\newcommand{\cyccomp}[1]{{\mathcal{C}}_{#1}}%cyclic tamari complex

\newcommand{\deconed}{\boldsymbol{\widetilde{\mathfrak{C}}}_n}

\newcommand{\cyclohedron}[1]{\boldsymbol{\mathfrak{B}}_{#1}}

\newcommand{\Match}{\mathfrak{m}} % a matching
\newcommand{\NCM}{\cM_{NC}} % non-crossing matching
\newcommand{\nc}{\mathfrak{nc}} % a matching


\newcommand{\Tam}[1]{\operatorname{Tam}_{#1}}
\newcommand{\Asso}{\operatorname{Asso}}
\newcommand{\AssoIJ}{\Asso_{I,\ol J}}
\newcommand{\pa}{\rho}%The path associated to a tree
\newcommand{\Cyclo}{\operatorname{Cyclo}}
\newcommand{\CycloIJ}{\Cyclo_{I,\ol J}}

\def\horiz{\operatorname{horiz}}

\newcommand{\ijtreesp}[2]{\mathsf{Tree}_{(#1,\ol{#2})}}
\newcommand{\ijtrees}{\ijtreesp{I}{J}}

\newcommand{\can}{c}%The cannopy associated to a tree

\DeclareMathOperator{\core}{core}%The cannopy associated to a tree

\newcommand{\cost}[1]{\kappa({#1})}%Cost of a lattice path

\renewcommand{\ij}{(i,\ol j)}
\renewcommand{\IJ}{(I,\ol {J})}
\newcommand{\nn}{([n],[\ol n])}

\newcommand{\IJary}{$\IJ$-ary}

\newcommand{\reverse}[1]{\overleftarrow{#1}}%reading the black and white sequence backwards

\newcommand{\ha}{\mathsf{h}}%height function for the associahedral triangulation
\newcommand{\hb}{\mathsf{h}}%height function for the cyclohedral triangulation
\newcommand{\arrgtA}{\mathcal{H}} % arrangement of tropical hyperplanes dual to associahedral triangulation
\newcommand{\arrgtB}{\mathcal{H}} % arrangement of tropical hyperplanes dual to cyclohedral triangulation

\newcommand{\lth}{\ell} % cyclic length of an IJ-edge
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%other

%overline
\newcommand{\ol}[1]{\overline{#1}}


%rightarrow
\newcommand{\ra}{\rightarrow}


% definitions
\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\newcommand{\defn}[1]{\emph{#1}} % emphasis of a definition

% todo
\usepackage{todonotes}
\newcommand{\camilo}[2][inline]{\todo[color=blue!30, #1, size=\footnotesize]{#2 \hfill ---Cam.}}
\newcommand{\cesar}[2][inline]{\todo[color=orange!30, #1, size=\footnotesize]{#2 \hfill ---Ces.}}
\newcommand{\arnau}[2][inline]{\todo[color=green!30, #1, size=\footnotesize]{#2 \hfill ---Ar.}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% figures
\graphicspath{{Figures/}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\usepackage{lipsum}

\title[Geometry of $\nu$-Tamari lattices in types $A$ and $B$]{Geometry of $\nu$-Tamari lattices in types $A$ and $B$}

\author{Cesar Ceballos\thanks{Supported by the Austrian Science Foundation FWF, grant F 5008-N15, in the framework of the Special Research Program ``Algorithmic and Enumerative Combinatorics''.}\addressmark{1}, Arnau Padrol\thanks{Supported by the program PEPS Jeunes Chercheur-e-s 2016 from the INSMI.}\addressmark{2} \and Camilo Sarmiento\thanks{Partially supported by CDS Magdeburg.}\addressmark{3}}

\address{\addressmark{1}Faculty of Mathematics, University of Vienna, Vienna, Austria \\ 
\addressmark{2}Sorbonne Universit\'es, Universit\'e Pierre et Marie Curie (Paris 6), IMJ-PRG (UMR 7586), Paris, France \\ \addressmark{3}Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany}

\received{\today}

 \abstract{In this extended abstract, we exploit the combinatorics and geometry of triangulations of products of simplices to reinterpret and generalize a number of constructions in Catalan combinatorics. In our framework, the main role of ``Catalan objects'' is played by $(I,\overline{J})$-trees: bipartite trees associated to a pair $(I,\overline{J})$ of finite index sets that stand in simple bijection with lattice paths weakly above a lattice path $\nu=\nu(I,\overline{J})$. Such trees label the maximal simplices of a triangulation of a subpolytope of the cartesian product of two simplices, 
 which provides a geometric realization of the $\nu$-Tamari lattice introduced by Pr\'eville-Ratelle and Viennot. 
Dualizing this triangulation, we obtain a polyhedral complex induced by an arrangement of tropical hyperplanes whose 1-skeleton realizes the Hasse diagram of the $\nu$-Tamari lattice, and thus generalizes the simple associahedron. Specializing to the Fuss-Catalan case realizes the $m$-Tamari lattices as $1$-skeleta of regular subdivisions of classical associahedra, giving a positive answer to a question of F. Bergeron. 
The simplicial complex underlying our triangulation has its $h$-vector given by a suitable generalization of the Narayana numbers. We propose it as a natural generalization of the classical simplicial associahedron, alternative to the rational associahedron of Armstrong, Rhoades and Williams.

Our methods are amenable to cyclic symmetry, which we use to present type-$B$ analogues of our constructions. Notably, we define a partial order that generalizes the type $B$ Tamari lattice, introduced independently by Thomas and Reading, along with corresponding geometric realizations.}

\keywords{Triangulations of products of simplices, Tamari lattices, Associahedra, Cyclohedra, Tropical hyperplanes.}


\begin{document}

\maketitle

\section{Introduction}

The Tamari lattice is a partial order on Catalan objects that has attracted considerable attention since it
was first introduced by Tamari in his doctoral thesis in 1951~\cite{TamariPhD}. Its covering relation can be described in terms of flips in polygon triangulations, 
rotations on binary trees and certain elementary transformation on Dyck paths.
Many generalizations of the Tamari lattice have been proposed. 
The $m$-Tamari lattice, a recent generalization to Fuss-Catalan Dyck paths introduced by Bergeron and Pr\'eville-Ratelle~\cite{BergeronPrevilleRatelle2012}, has raised much interest. 
It has been further generalized by Pr\'eville-Ratelle and Viennot to the set of lattice paths above any given lattice path~$\nu$, giving rise to the $\nu$-Tamari lattice~\cite{PrevilleRatelleViennot2014}.% 

One of the striking characteristics of the Tamari lattice is that its Hasse diagram can be realized as the edge graph of a polytope, the associahedron~\cite{CeballosSantosZiegler2015}. 
In~\cite[Figures~4 and~6]{Bergeron2012}, Bergeron presented geometric realizations of a few small $m$-Tamari lattices as the edge graph of a subdivision of an associahedron, and asked if such realizations exist in general. We provide a positive answer to this question (see \cref{fig:Cesar}).

\begin{theorem}[\cref{cor:IJtriang} and \cref{thm:nurealization}]\label{thm:realizations}
Let $\nu$ be a lattice path. 
The Hasse diagram of the $\nu$-Tamari lattice can be realized geometrically as:
\begin{enumerate}[leftmargin=29pt]
 \item\label{it:triang} the dual of a regular triangulation of a subpolytope of the Cartesian product of two simplices,
 \item\label{it:tropical} the edge graph of a polyhedral complex induced by an arrangement of tropical hyperplanes. 
\end{enumerate}
\end{theorem}

\begin{figure}[htbp]
\centering
\begin{tabular}{ccccc}
\includegraphics[width= 0.30\textwidth]{Figures/1Tamari4-2}&\qquad& 
\includegraphics[width= 0.22\textwidth]{Figures/4Tamari3}&\qquad&
\includegraphics[width= 0.30\textwidth]{Figures/2Tamari4}\\
$1$-Tamari $n=4$&&
$4$-Tamari $n=3$&&
$2$-Tamari $n=4$
\end{tabular}
\caption{Geometric realizations of $m$-Tamari lattices by cutting classical associahedra with tropical hyperplanes. Compare with~\cite[Figures 4, 5 and 6]{Bergeron2012}.}
\label{fig:Cesar}

\end{figure}

Our starting point is a ubiquitous triangulation $\asstri{n}$ of certain subpolytope {$\catblock{n}$} of the Cartesian product of two $n$-simplices which has been rediscovered in various contexts under different guises. To the best of our knowledge, its first appearances were in \cite{GelfandGraevPostnikov1997} as a triangulation of a root polytope and in \cite{PitmanStanley2002} as a fine mixed subdivision of the {Pitman-Stanley} polytope. Some of its recent occurrences are as a triangulation of a Gelfand-Tseltsin polytope~\cite{PetersenPylyavskyySpeyer2010}, a root polytope~\cite{Mes11a}, and an order polytope~\cite{SantosStumpWelker2014}. We call it the \defn{associahedral triangulation} because, combinatorially, it is the join of a simplex with the boundary complex of a simplicial $(n-1)$-associahedron. 

The fact that $\asstri{n}$ is embedded in the product of two simplices has several advantages. One can consider its restriction
to faces of $\productn$, which are also products of simplices. As we will see, for each lattice path $\nu$ there is a pair $I,\ol J\subseteq[n],[\ol {n}] $ such that the restriction of $\asstri{n}$ to its face $\productp{I}{\ol J}$ induces a triangulation $\asstri{I,\ol J}$ dual to $\Tam{\nu}$.
Its cells are indexed by \defn{$\IJ$-forests}, which endow $\nu$-Dyck paths with a full simplicial complex structure, the \defn{$\IJ$-Tamari complex}.
The $\ell$th entry of its $h$-vector is equal to the number of $\nu$-Dyck paths with exactly $\ell$ valleys, generalizing the classical Narayana numbers for classical Dyck paths. In the rational Catalan case, these numbers appeared in work of Armstrong, Rhoades, and Williams~\cite{ARW13}, who introduced an alternative simplicial complex based on lattice paths above a rational slope, called the rational associahedron.

As most ``non-crossing objects'', $\asstri{n}$ has a ``non-nesting'' analogue: the staircase triangulation of $\productn$ restricted to $\catblock{n}$. It already appeared as the standard triangulation of an order polytope in~\cite{Stanley1986}, and was also considered in the references mentioned above. In our previous work~\cite{CeballosPadrolSarmiento2015} we applied a cyclic shift to this triangulation to produce the \defn{Dyck path triangulation} of $\productn$ in our study of extendability of partial triangulations.

If we apply the same cyclic procedure to $\asstri{n}$, we obtain a flag regular triangulation~$\cyclotri{n}$ of $\productn$. Its maximal cells are indexed by centrally symmetric triangulations of a $(2n+2)$-gon and its dual complex is a cyclohedron. We call it the \defn{cyclohedral triangulation}. 
Restricting to its faces, we obtain a type~$B$ analogue of $\asstri{I,\ol J}$, whose maximal cells are indexed by \defn{cyclic $\IJ$-trees}. These trees can be naturally endowed with a poset structure, the \defn{cyclic $\IJ$-Tamari poset}, which generalizes the type $B$ Tamari lattice, independently discovered by Thomas~\cite{Thomas06} and Reading~\cite{Reading06}. Using the same techniques, we obtain type-$B$ analogues of \cref{thm:realizations} (\cref{cor:IJtriang} and \cref{thm:cyclicnurealization}).


\section{Type $A$}
\subsection{The associahedral triangulation}
\label{sec:assTri}

Let $\NN$ denote the set of natural numbers including the zero, and $\ol\NN$ the same set with numbers decorated with an overline. If $n$ is a natural number, define $[n]:=\{0,1,\ldots, n\}$, and likewise $[\ol n]:=\{\ol 0,\ol 1,\ldots, \ol n\}$. Regard $\NN\sqcup \ol \NN$ as the totally ordered set with covering relations $i\prec\ol i$ and $\ol i \prec i+1$. Given nonempty finite sets $I\subset\NN$ and $\ol J\subset \ol \NN$, denote by~\defn{$\bipartiteij$} the complete bipartite graph with node set $I\sqcup \ol J$ and arc set $\{(i,\ol j)\colon i\in I,\ \ol j\in\ol J\}$. To avoid confusion, we reserve the names \emph{vertices} and \emph{edges} exclusively for simplicial and polyhedral complexes, and call \emph{nodes} and \emph{arcs} the corresponding graph notions.


The Cartesian product of two standard simplices is the convex polytope:
\begin{equation*}
\product:=\conv\left\{ (\bfe_i, \bfe_j )\colon i \in [n],\ j\in[\ol m]\right\}\subset\RR^{n+m+2},
\end{equation*}
where $\bfe_i$ and $\bfe_{\ol j}$ denote the standard basis vectors of $\RR^{n+1}$ and $\RR^{m+1}$, respectively. We have introduced the overlined indices to distinguish the labels of the two factors.

Given a triangulation of an $(n+2)$-gon $P_{n+2}$, we define a subgraph of $\bipartitebn$ by mapping edges of the triangulation to arcs of $\bipartitebn$ as exemplified in \cref{fig:triang2tree} for $n=4$, where nodes of the parts $[n]$ and $[\ol n]$ are drawn black and white, respectively. It is not difficult to show that graphs obtained this way are spanning trees of $\bipartitebn$; we call them \defn{$\nn$-trees}.

\begin{figure}[htpb]
\centering 
 \includegraphics[width=\linewidth]{triang2tree2}
 \caption{From a triangulation of $P_6$ to spanning tree of $\bipartitebp{4}{4}$.}\label{fig:triang2tree}
\end{figure}

Spanning trees of $\bipartitebn$ can be identified with maximal subsimplices of $\productn$: a tree $T$ is identified with the simplex $\conv\{(\bfe_i,\bfe_{\ol j})\colon \ij\in T\}$~\cite{DeLoeraRambauSantos2010}. This identification leads to the following theorem, which has been rediscovered in a number of contexts.

\begin{theorem}[{\cite{GelfandGraevPostnikov1997, PitmanStanley2002}}]\label{thm:asstriang}
The set of $\nn$-trees indexes the maximal simplices of a flag regular triangulation of the subpolytope $\catblock{n}$ of $\productn$, defined as:
\begin{equation*}
\catblock{n}:=\conv\left\{ (\bfe_i, \bfe_{\ol j} ) \colon 0\leq i\leq \ol j\leq n\right\}\subseteq\productn.
\end{equation*}  
We call it the \defn{$n$-associahedral triangulation $\asstri{n}$} because two maximal simplices are adjacent if and only if the corresponding triangulations of $P_{n+2}$ differ by a flip.
\end{theorem}

Faces of $\product$ are polytopes of the form $\productIJ:=\conv\left\{ (\bfe_i, \bfe_{\ol j} )\ :\  i\in I,  \ol j\in\ol J\right\}$, where $I\subseteq [n],\ol J\subseteq[\ol n]$. Given such a pair $(I,\ol J)$ of subsets, it is natural to consider the restriction $\catblock{I,\ol J}:=\catblock{n}\cap \productIJ$ and the corresponding restriction of the associahedral triangulation $\asstri{n}$ to $\catblock{I,\ol J}$. We call this restricted triangulation the \defn{$\IJ$-associahedral triangulation}. Its maximal simplices are given by $\IJ$-trees, which are characterized as follows.

\begin{definition}\label{def:IJtree}
Let $I\subset\NN$ and $\ol J\subset \ol \NN$ be nonempty finite subsets. An \defn{$\IJ$-forest} is a subgraph of $\bipartiteij$ that is
\begin{enumerate}
 \item \textbf{Increasing:} each arc $(i,\ol j)$ fulfills $i\prec \ol j$; and
 \item \textbf{Non-crossing:} it does not contain two arcs $(i,\ol j)$ and $(i', \ol j')$ satisfying ${i\prec  i'\prec \ol j \prec \ol j '}$. 
\end{enumerate} 
An \defn{$\IJ$-tree} is a maximal $\IJ$-forest. An $\IJ$-tree is shown in \cref{fig:IJtree2path}.
\end{definition}

\begin{corollary}
\label{cor:IJtriang}
Let $I\subset \NN$, $\ol J\subset \ol \NN$ be nonempty finite sets. The set of $\IJ$-trees indexes the maximal simplices of a flag regular triangulation of $\catblock{I,\ol J}$, induced by the height function $\ha\ij=-(j-i)^2$. We call it the \defn{$\IJ$-associahedral triangulation $\asstri{I,\ol J}$}.  
\end{corollary}

\subsection{The \protect$\IJ$-Tamari lattice and $\nu$-Dyck paths}
\label{sec:assTamari}

We say that two $\IJ$-trees $T$ and $T'$ are related by a \defn{flip} if there are arcs $\ij$ and $(i',\ol{j'})$ such that $T':=T\setminus \ij\cup (i',\ol{j'})$. 
Such flip can occur if and only if $\ij$ is neither a leaf nor the arc $(\min I,\max\ol J)$.  If $i'>i$ and $j'>j$, we say that $T'$ is obtained from $T$ by an \defn{increasing flip}, and symbol this by the relation \defn{$T<_{I,\ol J} T'$}.

\begin{lemma}\label{lem:IJposet}
The transitive closure of the relation $T <_{I,\ol J} T'$ is a partial order on the set of $\IJ$-trees that defines a lattice.  We call it the \defn{$\IJ$-Tamari lattice $\Tam{I,\ol J}$}.
\end{lemma}

The significance of the $\IJ$-Tamari lattice stems from the close relation between $\IJ$-trees and lattice paths, which we now explain. Recall that a lattice path $\nu$ is a sequence of east ($\sfE$) and north ($\sfN$) steps in $\ZZ^2$ starting at $(0,0)$. A \defn{$\nu$-path} is a lattice path with the same endpoints as $\nu$ and lying weakly above $\nu$.
  
Let $I\subset\NN, \ol J\subset \ol \NN$ be nonempty finite subsets such that $\min I\sqcup \ol J \in I$ and $\max I\sqcup \ol J\in \ol J$ (this implies that $\IJ$-trees are trees in the graph-theoretical sense). We can assume without loss of generality that $I\sqcup J=[n]$ is a partition, because for the definition of $\IJ$-trees only the relative positions of $I$ and $\ol J$ matter. 

To $\IJ$ we associate a lattice path \defn{$\nu\IJ$} from $(0,0)$ to $(|I|-1,|\ol J|-1)$ constructed as follows: for $1\leq k\leq n-1$, the $k$-th step of $\nu\IJ$ is an east step $\sfE$ if $k\in I$ and a north step $\sfN$ if $\ol k\in \ol J$. Now, to an $\IJ$-tree $T$ we associate the unique lattice path $\pa(T)$ from $(0,0)$ to $(|I|-1,|\ol J|-1)$ having at height $k-1$ as many lattice points as the degree of the $k$th node of $\ol J$ in $T$. We illustrate this construction in \cref{fig:IJtree2path}.

\begin{figure}[h]
\centering 
 \includegraphics[width=\textwidth]{IJtree2path2}
 \caption{An $(I,\ol J)$-trees for $I=\{0,1,2,5,6,9\}$ and $\ol J=\{\ol 3,\ol 4, \ol 7,\ol 8, \ol {10}\}$, and the corresponding $\nu(I,\ol J)$-path $\pa(T)$.}\label{fig:IJtree2path}
\end{figure}

\begin{proposition}\label{prop:IJtree2vpath}
Let $I,\ol J$ be nonempty subsets of $\NN$ with $\min (I\sqcup \ol J)\in I$ and $\max (I\sqcup \ol J)\in \ol J$, and let $\nu=\nu(I,\ol J)$. 
Then $\pa$ is a bijection from the set of $(I,\ol J)$-trees to the set of $\nu$-paths.
 Moreover, for each path $\nu$ from $(0,0)$ to $(a,b)$ there is a partition $I,\ol J$ of $[a+b+1]$ such that $\nu(I,\ol J)= \nu$.
\end{proposition}

In~\cite{PrevilleRatelleViennot2014}, Pr\'eville-Ratelle and Viennot introduced a lattice structure on the set of $\nu$-paths that they called the \defn{$\nu$-Tamari lattice}. It extends the classical Tamari lattice on Dyck paths, as well as its generalizations for Fuss-Catalan paths. As it turns out, this lattice is equivalent to the $\IJ$-Tamari lattice under the bijection~$\pa$. An example of this equivalence is shown in \cref{fig:TamariTreesnPaths}.

\begin{theorem}\label{prop:IJTamarivTamari}
The $\IJ$-Tamari lattice $\Tam{I,\ol J}$ is isomorphic to the $\nu\IJ$-Tamari lattice $\Tam{\nu\IJ}$.
\end{theorem}

\begin{figure}[h]
\centering 
 \includegraphics[width=0.6\textwidth]{TamariTreesnPaths}
 \caption{The $\IJ$-Tamari lattice for $I=\{0,1,3,4,6,7\}, \ol J=\{\ol 2, \ol 5, \ol 8\}$, next to the $\nu\IJ$-Tamari lattice.}
 \label{fig:TamariTreesnPaths}
\end{figure}

\subsection{The \protect$\IJ$-Tamari complex and \protect$\IJ$-Narayana numbers}


We call the simplicial complex underlying the $\IJ$-associa\-he\-dral triangulation $\asstri{I,\ol J}$ the \defn{$\IJ$-Tamari complex $\asscomp{I,\ol J}$}. It shares many properties with boundaries of simplicial associahedra. For instance, the links of its faces are joins of Tamari complexes.
It has a nice interplay with the $\IJ$-Tamari order, which can be used to define a shelling of $\asscomp{I,\ol J}$ that brings about a natural expression for the entries of the $h$-vector of $\asscomp{I,\ol J}$.

\begin{lemma}\label{lem:shellingorder}
Let $\cO=(T_1,T_2,\ldots, T_r)$ be an ordering of the $\IJ$-trees that is a linear extension of the $\IJ$-Tamari lattice or of its opposite lattice. Then $\cO$ is a shelling order for $\asscomp{I,\ol J}$.
\end{lemma}

\begin{theorem}
\label{thm:thehvector}
The $h$-vector $(h_0,h_1,\ldots)$ of the $\IJ$-Tamari complex is determined by:
\begin{align*}
\label{eq:thehvector}
h_\ell&=\left|\left\{ T\colon \text{ $\IJ$-tree with exactly $\ell$ non-leaf nodes in $\ol J\setminus\{\ol j_{\max}\}$} \right\}\right| \\
&=\text{number of $\nu\IJ$-paths with exactly $\ell$ valleys},
\end{align*}
where a valley of a path is an occurrence of $\sfE\sfN$.
\end{theorem}

In analogy to the $h$-vectors of classical simplicial associahedra and their combinatorial interpretation, which \cref{thm:thehvector} generalizes, we designate the entries of the $h$-vector of $\asscomp{I,\ol J}$ the \defn{$\IJ$-Narayana numbers}, or the \defn{$\nu$-Narayana numbers} when $\nu=\nu\IJ$.

\subsection{The \protect$\IJ$-associahedron tropically}
\label{sec:tropicalA}

In~\cite{DevelinSturmfels2004}, Develin and Sturmfels exhibited a beautiful duality between regular triangulations of $\product$ and combinatorial types of generic arrangements of $n+1$ tropical hyperplanes in tropical projective space $\TT\PP^m$. It was further studied combinatorially in~\cite{ArdilaDevelin2009} and extended to subpolytopes of $\product$ in~\cite{FinkRincon2015}. Applying this duality to the $\IJ$-associahedral triangulation allows us to propose a notion of \defn{$\IJ$-associahedron}. It generalizes the geometric realization of the Hasse diagram of the classical Tamari lattice as the graph of the (simple) associahedron. 
We provide a direct construction as a polyhedral complex. To this end, let $\ha:\{(i,\ol j)\in I\times \ol J\colon i\preceq \ol j \}\to \RR$ be the height function $\ha\ij=-(j-i)^2$, which induces $\asstri{I,\ol J}$ as a regular triangulation of $\catblock{I,\ol J}$ (cf. \cref{thm:asstriang}). We need the following characterization of interior simplices of $\asstri{I,\ol J}$

\begin{lemma}
\label{lem:interiorsimplex}
The interior simplices of the $\IJ$-associahedral complex $\asscomp{I,\ol J}$ are the \defn{$\IJ$-forests} that include the arc $(\min I,\max \ol J)$ and have no isolated nodes. We refer to such {$\IJ$-forests} as \defn{covering $\IJ$-forests}.
\end{lemma}

\begin{definition}\label{def:nuassociahedronH}
The \defn{$\IJ$-associahedron $\Asso_{I,\ol J}(\ha)$} is the polyhedral complex in $\RR^{|J|-1}$ with vertices $\sfg(T)$, as $T$ ranges over $\IJ$-trees, whose $\ol k$th coordinates equal:
\begin{equation}\label{eq:g_treecyclic}
\sfg(T)_{\ol k}:=\sum_{(i,\ol j)\in P(\ol k)}\pm \ha({i,\ol j}),\qquad \ol k\in\ol J\setminus\{\max\ol J\},
\end{equation}
where $P({\ol k})$ is the sequence of arcs traversed in the unique oriented path from~$\ol k$ to~$\max \ol J$ in $T$ and 
the sign of each summand is positive if $(i,\ol j)$ is traversed from $\ol j$ to $i$ and negative otherwise. 

The cells of $\Asso_{I,\ol J}(\ha)$ are given by convex polytopes $\sfg(F)$, with $F$ ranging over covering $(I,\ol J)$-forests, whose dimension is one less than the number of connected components of $F$, and whose vertices are given by:
\begin{equation}\label{eq:g_forestcyclic}
\sfg(F)=\conv\left\{ \sfg(T)\colon \text{ $T$ is a $(I,\ol J)$-tree containing $F$} \right\}.
\end{equation}
\end{definition}

\begin{theorem}
\label{thm:nurealization}
The $\IJ$-associahedron $\Asso_{I,\ol J}(\ha)$ is a polyhedral complex whose poset of cells is anti-isomorphic to the poset of interior faces of the $\IJ$-Tamari complex. 
Its 1-skeleton, oriented according to a linear function, is isomorphic to the  Hasse diagram of the $\IJ$-Tamari lattice.
\end{theorem}

We have depicted two $\IJ$-associahedra in \cref{fig:ExampleIJasso}; compare the one on the left with \cref{fig:TamariTreesnPaths}. We warmly invite the reader to reproduce them in a piece of paper.

 \begin{figure}[hptb]
 \begin{center}
  \includegraphics[width=\linewidth]{IJassociahedra}
  \caption{$\IJ$-associahedra for $I=\{0,1,3,4,6,7\},\ol J=\{\ol 2,\ol 5,\ol 8\}$ (left) and to $I=\{0,1,2,3\}, \ol J=\{\ol 3, \ol 4, \ol 5\}$ (right).}\label{fig:ExampleIJasso}
\end{center}
 \end{figure}

\cref{fig:ExampleIJasso} shows that $\IJ$-associahedra are not convex in general. The following theorem characterizes convexity and answers F. Bergeron's question affirmatively~\cite[Section 8]{Bergeron2012}.

\begin{theorem}\label{thm:supportAssociahedron}
Let $\ol J'=\{\ol j\in \ol J\ \colon\ \exists\ i_1\prec i_2 \prec \ol j\}$.
The $\IJ$-associahedron $\AssoIJ(\ha)$ is convex if and only if $I\sqcup \ol J'\setminus \max {\ol J}$ does not have a consecutive pair of elements of $\ol J$. In this case, $\AssoIJ(\ha)$ is a regular polyhedral  subdivision of a classical associahedron of dimension $(|\ol J'|-1)$ into cells that are Cartesian products of classical associahedra.
\end{theorem}

\section{Type $B$}
\subsection{The cyclohedral triangulation}

The map from triangulations of an $(n+2)$-gon to spanning trees of $\bipartitebn$ in \cref{sec:assTri} can be extended to a map on \emph{centrally symmetric triangulations} of a $(2n+2)$-gon $P_{2n+2}$ (hereafter \defn{cs-triangulations}), as shown in \cref{fig:cstriang2tree}. We call the resulting graphs \defn{cyclic $\nn$-trees}. We draw them on the surface of a cylinder, with arcs that possibly wind around~it.

\begin{figure}[htpb]
 \centering 
 \includegraphics[width=.9\linewidth]{cstriang2tree2}
 \caption{From a cs-triangulation to a non-crossing alternating tree on the cylinder.}\label{fig:cstriang2tree}
\end{figure}

\begin{theorem}\label{thm:cyclohedrontriangulation}
The set of cyclic $\nn$-trees indexes the maximal simplices of a flag regular triangulation of $\productn$. We call it the \defn{$n$-cyclohedral triangulation~$\cyctri{n}$} because two maximal simplices are adjacent if and only if the corresponding cs-triangulations differ by a flip.
\end{theorem}

Considering the restriction of $\cyctri{n}$ to faces of $\product$ leads to the following notion.

\begin{definition}\label{def:cyclicIJtree}
Let $I\subset [n]$ and $\ol J\subset [\ol n]$ be nonempty subsets, for some $n\in\NN$. A \defn{cyclic $(I,\ol J)$-forest} is a subgraph $F$ of $\bipartitep{I}{J}$ that is \textbf{cyclically non-crossing}, in the following sense:
\begin{align}
\label{eq:cycliccross}
\begin{cases}
(i,\ol j),\ (i',\ol j') \in F,\text{ and} \\
j-i'< j-i \pmod{n+1}
\end{cases} & \implies & j'-i' \leq j-i' \pmod{n+1}
\end{align}
 A \defn{cyclic $(I,\ol J)$-tree} is a maximal cyclic $(I,\ol J)$-forest.
\end{definition}

\begin{corollary}
Let $I\subset [n]$ and $\ol J\subset [\ol n]$ be nonempty subsets. The set of cyclic $(I,\ol J)$-trees indexes the maximal simplices of a flag regular triangulation of $\productp{I}{J}$, induced by the height function $\hb=\sqrt{j-i\pmod{n+1}}$. We call it the \defn{$\IJ$-cyclohedral triangulation $\cyctri{I,\ol J}$}.
\end{corollary}

\subsection{The cyclic \protect$\IJ$-Tamari poset}

Let $T,T'$ be cyclic $\IJ$-trees such that $T'=T\setminus \ij \cup (i',\ol{j'})$. As in \cref{sec:assTamari}, we say that $T'$ is obtained by an \defn{increasing flip} from $T$ if $i'>i$, and write $T <_{\IJ} T'$ in this case.

\begin{lemma}
\label{lem:cyclicIJposet}
 The transitive closure of the relation $T <_{I,\ol J} T'$ is a partial order on the set of cyclic $(I,\ol J)$-trees. We call it the the \defn{cyclic $\IJ$-Tamari poset $\Tam{I,\ol J}^B$.}
\end{lemma}

In~\cite{Thomas06}, Thomas introduced a partial order on the cs-triangulations of a $(2n+2)$-gon, which he recognized as the type $B_n$ Tamari lattice. Based on the following observation, we present the cyclic $\IJ$-Tamari poset as a generalization of the type $B_n$ Tamari lattice.

\begin{lemma}
\label{lem:ThomasEqualsIJ}
The $B_n$ Tamari lattice of~\cite{Thomas06} is isomorphic to the cyclic $\nn$-Tamari poset.
\end{lemma}

\begin{remark}
As the name suggests, the cyclic $\IJ$-Tamari poset is in general \textbf{not a lattice}. We encourage the reader to check this for $I=\{0,3,4\}$ and $\ol J=\{\ol 1,\ol 2\}$.
\end{remark}


\subsection{The cyclic \protect$\IJ$-Tamari complex}

Let $I\subset\NN,\ol J\subset \ol\NN$ be nonempty finite subsets. The \defn{cyclic $\IJ$-Tamari complex $\cyccomp{I,\ol J}$} is the simplicial complex underlying the $\IJ$-cyclohedral triangulation $\cyctri{I,\ol J}$. Its $h$-vector can be computed using its geometric realization as the triangulation $\cyctri{I,\ol J}$ of~$\productIJ$.

\begin{theorem}
\label{thm:typeBhVector}
The $h$-vector of $\cyccomp{I,\ol J}$ has entries $h_k(\cyccomp{I,\ol J})=\binom{|I|-1}{k}\binom{|\ol J|-1}{k}$.
\end{theorem}

The Fuss-Catalan analogues of the Narayana numbers of type $B_n$ are obtained when $|I|=mn+1$ and $|J|=n+1$.

\subsection{The cyclic \protect$\IJ$-associahedron tropically}
We conclude this extended abstract with a notion of $\IJ$-cyclohedron parallel to the $\IJ$-associahedron from \cref{sec:tropicalA}. The development imitates that of \cref{sec:tropicalA}, so we merely present the corresponding results. Let $\hb\colon\{(i,\ol j)\in [n]\times[\ol n]\}\to \RR$ be the height function $\hb\ij=\sqrt{j-i\pmod {n+1}}$, which induces $\cyctri{I,\ol J}$ as a regular triangulation of~$\productIJ$.

\begin{lemma}\label{lem:cyclicinteriorsimplex}
The interior simplices of $\cyccomp{I,\ol J}$ are naturally indexed by cyclic \defn{$\IJ$-forests} that have no isolated nodes. We refer to such cyclic {$\IJ$-forests} as \defn{covering cyclic $\IJ$-forests}.
\end{lemma}

\begin{definition}\label{def:nucyclohedron}
The \defn{$\IJ$-cyclohedron $\Cyclo_{I,\ol J}(\hb)$} is the polyhedral complex in $\RR^{|J|-1}$ with vertices $\sfg(T)$, as $T$ ranges over cyclic $\IJ$-trees, with coordinates given by~\eqref{eq:g_treecyclic}. The cells of $\Cyclo_{I,\ol J}(\hb)$ are given by convex polytopes $\sfg(F)$, with $F$ ranging over covering cyclic $(I,\ol J)$-forests, defined analogously as in \eqref{eq:g_forestcyclic}.
\end{definition}

\begin{theorem}
\label{thm:cyclicnurealization}
The $\IJ$-cyclohedron $\Cyclo_{I,\ol J}(\hb)$ is a polyhedral complex whose poset of cells is anti-isomorphic to the poset of interior faces of the cyclic $\IJ$-Tamari complex. 
In particular, two vertices are connected if and only if the corresponding cyclic $\IJ$ trees are related by a flip. That is, the edge graph of $\Cyclo_{I,\ol J}(\hb)$ is isomorphic to the Hasse diagram of the cyclic $\IJ$-Tamari poset.
\end{theorem}

\begin{theorem}\label{thm:supportCyclohedron}
Let $I,\ol J$ be finite subsets of $\NN$ with $|I|\geq 2$ and $|\ol J|\geq 3$. Then $\supp(\CycloIJ(\hb))$ is convex if and only if 
$\ol J$ does not have a cyclically consecutive pair of elements.
In this case, $\CycloIJ(\hb)$ is a regular polyhedral subdivision of a classical cyclohedron of dimension $(|\ol J|-1)$ into cells that are Cartesian products of classical associahedra and at most one clasical cyclohedron.
\end{theorem}

\cref{fig:IJcyclohedron} shows an $\IJ$-cyclohedron that is a subdivision of a classical cyclohedron.

 \begin{figure}[hptb]
 \begin{center}
  \includegraphics[width=0.7\linewidth]{IJcyclohedron}
  \caption{$\IJ$-cyclohedron for $I=\{0,1,3,4,6,7\}, \ol J=\{\ol 2, \ol 5, \ol 8\}$.}\label{fig:IJcyclohedron}
  \end{center}
 \end{figure}


\acknowledgements{We want to thank Fr\'ed\'eric Chapoton for showing us a beautiful picture of the $2$-Tamari lattice for $n=4$, posted in Fran\c{c}ois Bergeron's web page, which impulsed this project; and Michael Joswig, Georg Loho, Vincent Pilaud, Francisco Santos and Christian Stump for many interesting discussions.}

 \printbibliography



\end{document}
